A computer, smartphone, or other device may be configured to execute code compiled to the native instruction set of its microprocessor, in addition to certain non-native instruction sets. When encountered by the microprocessor, blocks of non-native instructions may be translated to native instructions and may also be optimized—e.g., to increase speed of execution. Non-native instructions typically will not be translated until they are encountered. Accordingly, it will often be the case that a block of code undergoing translation could include various branch instructions to additional code still awaiting translation. In that event, a chaining stub may be used at every branch instruction that targets untranslated code. The chaining stub may direct the system to search an instruction cache for an existing translation of the branch target, and, if a translation is found, to redirect the instruction pointer to that translation. If the translation is not found, then the non-native code block may be submitted for translation and/or executed in an alternative manner. However, the search for pre-existing translations may be undesirably slow in some scenarios.